package org.example;

import java.util.*;

// 二叉树心法（构造篇）
// https://labuladong.online/algo/data-structure/binary-tree-part2/
public class BinaryTree2 {
    // 二叉树解题的思维模式分两类
    // 1. 是否可以通过遍历一遍二叉树得到答案？如果可以，用一个traverse函数配合外部变量来实现，这叫【遍历】的思维模式
    // 2. 是否可以定义一个递归函数，通过子问题（子树）的答案推导出原问题的答案？如果可以，写出这个递归函数的定义，并充分利用这个函数的返回值，这叫【分解问题】的思维模式
    // 无论使用哪种思维模式，你都需要思考：
    // 如果单独抽出一个二叉树节点，它需要做什么事情？需要在什么时候（前/中/后序位置）做？其他的节点不用你操心，递归函数会帮你在所有节点上执行相同的操作。

    // 【二叉树的构造问题一般都是使用「分解问题」的思路：构造整棵树 = 根节点 + 构造左子树 + 构造右子树。】

    // 【构造最大二叉树】
    // 654. 最大二叉树
    // 给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:
    // 创建一个根节点，其值为 nums 中的最大值。
    // 递归地在最大值 左边 的 子数组前缀上 构建左子树。
    // 递归地在最大值 右边 的 子数组后缀上 构建右子树。
    // 返回 nums 构建的 最大二叉树 。
    // 输入：nums = [3,2,1,6,0,5]
    // 输出：[6,3,5,null,2,0,null,null,1]
    // 解释：递归调用如下所示：
    // - [3,2,1,6,0,5] 中的最大值是 6 ，左边部分是 [3,2,1] ，右边部分是 [0,5] 。
    //    - [3,2,1] 中的最大值是 3 ，左边部分是 [] ，右边部分是 [2,1] 。
    //        - 空数组，无子节点。
    //        - [2,1] 中的最大值是 2 ，左边部分是 [] ，右边部分是 [1] 。
    //            - 空数组，无子节点。
    //            - 只有一个元素，所以子节点是一个值为 1 的节点。
    //    - [0,5] 中的最大值是 5 ，左边部分是 [0] ，右边部分是 [] 。
    //        - 只有一个元素，所以子节点是一个值为 0 的节点。
    //        - 空数组，无子节点。
    static class ConstructMaximumBinaryTree {
        public TreeNode constructMaximumBinaryTree(int[] nums) {
            return build(nums, 0, nums.length - 1);
        }

        // 定义：将nums[lo..hi]构造成条件的树，返回根节点
        TreeNode build(int[] nums, int lo, int hi) {
            // base case
            if (lo > hi) {
                return null;
            }
            // 找到数组中的最大值和对应的索引
            int index = -1;
            int maxVal = Integer.MIN_VALUE;
            for (int i = lo; i <= hi; i++) {
                if (maxVal < nums[i]) {
                    index = i;
                    maxVal = nums[i];
                }
            }
            // 先构造出根节点
            TreeNode root = new TreeNode(maxVal);
            // 递归调用构造左右子树
            root.left = build(nums, lo, index - 1);
            root.right = build(nums, index + 1, hi);
            return root;
        }
    }

    // 叉树的遍历方式分为前序、中序和后序，它们的区别在于根节点的访问顺序。
    // 前序遍历：根→左→右
    // 中序遍历：左→根→右
    // 后序遍历：左→右→根

    // 通过前序和中序遍历结果构造二叉树
    // 105. 从前序与中序遍历序列构造二叉树
    // 给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
    // 示例1：
    // 输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
    // 输出: [3,9,20,null,null,15,7]
    // 示例 2:
    //
    // 输入: preorder = [-1], inorder = [-1]
    // 输出: [-1]

    // 基本思路：我们肯定要想办法确定根节点的值，把根节点做出来，然后递归构造左右子树即可。
    static class BuildTree1 {
//        前序遍历的特点
//        void traverse(TreeNode root){
//            // 前序遍历
//            preorder.add(root.val);
//            traverse(root.left);
//            traverse(root.right);
//        }
//        中序遍历的特点
//        void traverse(TreeNode root){
//            traverse(root.left);
//            // 中序遍历
//            inorder.add(root.val);
//            traverse(root.right);
//        }

        // 存储inorder中值到索引的映射(题目说二叉树节点的值不存在重复，所以可以使用一个 HashMap 存储元素到索引的映射)
        HashMap<Integer, Integer> valToIndex = new HashMap<>();

        public TreeNode buildTree(int[] preorder, int[] inorder) {
            for (int i = 0; i < inorder.length; i++) {
                valToIndex.put(inorder[i], i);
            }
            return build(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
        }

        // build函数的定义：
        // 若前序遍历数组为 preorder[preStart..preEnd]，
        // 中序遍历数组为 inorder[inStart..inEnd]，
        // 构造二叉树，返回该二叉树的根节点
        TreeNode build(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd) {
            if (preStart > preEnd) {
                return null;
            }
            // root节点对应的值就是前序遍历数组的第一个元素
            int rootVal = preorder[preStart];
            // rootVal在中序遍历数组中的索引
            int index = valToIndex.get(rootVal);

            int leftSize = index - inStart;

            // 先构造出当前根节点
            TreeNode root = new TreeNode(rootVal);
            // 递归构造左右子树
            root.left = build(preorder, preStart + 1, preStart + leftSize, inorder, inStart, index - 1);
            root.right = build(preorder, preStart + leftSize + 1, preEnd, inorder, index + 1, inEnd);
            return root;
        }
    }

    // 通过后序和中序遍历结果构造二叉树
    // 106. 从中序与后序遍历序列构造二叉树
    // 给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。
    // 示例 1:
    // 输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
    // 输出：[3,9,20,null,null,15,7]

    // void traverse(TreeNode root) {
    //    traverse(root.left);
    //    traverse(root.right);
    //    // 后序遍历
    //    postorder.add(root.val);
    //
    // }
    //
    // void traverse(TreeNode root) {
    //    traverse(root.left);
    //    // 中序遍历
    //    inorder.add(root.val);
    //    traverse(root.right);
    // }
    static class BuildTree2 {
        // 存储inorder中值到索引的映射
        HashMap<Integer, Integer> valToIndex = new HashMap<>();

        public TreeNode buildTree(int[] inorder, int[] postorder) {
            for (int i = 0; i < inorder.length; i++) {
                valToIndex.put(inorder[i], i);
            }
            return build(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);
        }

        // 定义：中序遍历数组为 inorder[inStart..inEnd]，
        // 后序遍历数组为 postorder[postStart..postEnd]，
        // build 函数构造这个二叉树并返回该二叉树的根节点

        TreeNode build(int[] inorder, int inStart, int inEnd, int[] postorder, int postStart, int postEnd) {
            if (inStart > inEnd) {
                return null;
            }
            // root节点对应的值就是后序遍历数组的最后一个元素
            int rootVal = postorder[postEnd];
            // rootVal在中序遍历数组中的索引
            int index = valToIndex.get(rootVal);
            // 左子树的节点个数
            int leftSize = index - inStart;
            TreeNode root = new TreeNode(rootVal);
            // 递归构造左右子树
            root.left = build(inorder, inStart, index - 1, postorder, postStart, postStart + leftSize - 1);
            root.right = build(inorder, index + 1, inEnd, postorder, postStart + leftSize, postEnd - 1);
            return root;
        }
    }

    // 通过后序和前序遍历结果构造二叉树
    // 889. 根据前序和后序遍历构造二叉树
    // 通过前序中序，或者后序中序遍历结果可以确定唯一一棵原始二叉树，但是通过前序后序遍历结果无法确定唯一的原始二叉树。
    // 基本思路：
    // 1、首先把前序遍历结果的第一个元素或者后序遍历结果的最后一个元素确定为根节点的值。
    // 2、然后把前序遍历结果的第二个元素作为左子树的根节点的值。
    // 3、在后序遍历结果中寻找左子树根节点的值，从而确定了左子树的索引边界，进而确定右子树的索引边界，递归构造左右子树即可。
    static class BuildTree3 {
        // 存储postorder中值到索引的映射
        HashMap<Integer, Integer> valToIndex = new HashMap<>();

        public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
            for (int i = 0; i < postorder.length; i++) {
                valToIndex.put(postorder[i], i);
            }
            return build(preorder, 0, preorder.length - 1, postorder, 0, postorder.length - 1);
        }

        // 定义：根据 preorder[preStart..preEnd] 和 postorder[postStart..postEnd]
        // 构建二叉树，并返回根节点。
        TreeNode build(int[] preorder, int preStart, int preEnd, int[] postorder, int postStart, int postEnd){
            if (preStart > preEnd){
                return null;
            }
            if (preStart == preEnd){
                return new TreeNode(preorder[preStart]);
            }

            // root节点对应的值就是前序遍历数组的第一个元素
            int rootVal = preorder[preStart];
            // root.left的值是前序遍历第二个元素
            // 通过前序和后序遍历构造二叉树的关键在于通过左子树的根节点
            // 确定preorder和postorder中左右子树的元素区间
            int leftRootVal = preorder[preStart + 1];
            // leftRootVal在后序遍历数组中的索引
            int index = valToIndex.get(leftRootVal);
            // 左子树的元素个数
            int leftSize = index - postStart + 1;
            // 先构造出当前根节点
            TreeNode root = new TreeNode(rootVal);
            // 递归构造左右子树
            // 根据左子树的根节点索引和元素个数推导左右子树的索引边界
            root.left = build(preorder, preStart + 1, preStart + leftSize, postorder, postStart, index);
            root.right = build(preorder, preStart + leftSize + 1, preEnd, postorder, index + 1, postEnd-1);
            return root;
        }

        // 最后呼应下前文，二叉树的构造问题一般都是使用「分解问题」的思路：【构造整棵树 = 根节点 + 构造左子树 + 构造右子树。】
        // 先找出【根节点】，然后根据根节点的值找到左右子树的元素，进而递归构建出左右子树。
    }


}






























